package 递归回溯.二维版;

public class No695岛屿的最大面积 {

    /**
     * 给定一个包含了一些 0 和 1 的非空二维数组 grid 。
     * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，
     * 这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
     * 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
     *
     * 示例 1:
     * [[0,0,1,0,0,0,0,1,0,0,0,0,0],
     *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
     *  [0,1,1,0,1,0,0,0,0,0,0,0,0],
     *  [0,1,0,0,1,1,0,0,1,0,1,0,0],
     *  [0,1,0,0,1,1,0,0,1,1,1,0,0],
     *  [0,0,0,0,0,0,0,0,0,0,1,0,0],
     *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
     *  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
     * 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
     *
     * 示例 2:
     * [[0,0,0,0,0,0,0,0]]
     * 对于上面这个给定的矩阵, 返回 0。
     */

    private int allLength;
    private int itemLength;
    private int[][] arr;
    private boolean[][] flag;
    //上 右 下 左
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};

    public int maxAreaOfIsland(int[][] grid) {
        this.allLength=grid.length;
        this.itemLength=grid[0].length;
        this.arr=grid;
        this.flag=new boolean[allLength][itemLength];
        int maxCount=0;
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                if(arr[i][j]==1&&!flag[i][j]){
                    //是陆地&&未探索
                    maxCount=Math.max(dfs(i,j,0),maxCount);
                }
            }
        }
        return maxCount;
    }

    private int dfs(int startX,int startY,int count){
        flag[startX][startY]=true;
        for (int i = 0; i < 4; i++) {
            int newX=startX+around[i][0];
            int newY=startY+around[i][1];
            if(newX>=0&&newX<=allLength-1&&newY>=0&&newY<=itemLength-1
                    &&!flag[newX][newY]&&arr[newX][newY]==1){
                count=dfs(newX,newY,count);
            }
        }
        return count+1;
    }

    public static void main(String[] args) {

        No695岛屿的最大面积 n=new No695岛屿的最大面积();
        int[][] arr={{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
        int i = n.maxAreaOfIsland(arr);
        System.out.println(i);
    }

}
